import java.util.Random;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
//        int[] nums = new int[]{1,5,1,9,2,4,3,1};
//        quickSort(0, nums.length-1, nums);
//        for(int e: nums) {
//            System.out.print(e + " ");
//        }

        int[] arr = new int[]{3,2,3,1,2,4,5,5,6};
        System.out.println(s.findKthLargest(arr, 4));
    }

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(k, 0, nums.length-1, nums);
    }

    public static int quickSelect(int k, int left, int right, int[] nums) {
        /**
         * 快速选择算法*/
        // 1 递归出口
        // -注意：当left==right时，表示第k大就是当前元素（因为k必定有效）
        if(left == right) {
            return nums[left];
        }
        // 2 随机选择基准值
        int key = nums[left + random.nextInt(right - left + 1)];
        // 3 数组分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < key) {
                swap(i++, ++l, nums);
            } else if(nums[i] == key) {
                i++;
            } else {
                swap(i, --r, nums);
            }
        }
        // 4 根据排序情况选择执行操作
        if(right - r + 1 >= k) {
            // -第k大在大于区间
            return quickSelect(k, r, right, nums);
        } else if(right - l >= k) {
            // -第k大在等于区间
            return key;
        } else {
            // -第k大在小于区间
            // -在新的区间中，第k大已经改变，需要同步更新（因为右侧舍弃，在新区间中，k要对应更新）
            return quickSelect(k - right + l, left, l, nums);
        }
    }

    public static void swap(int a, int b, int[] nums) {
        /**
         * 交换demo*/
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    public static Random random = new Random();

    public int[] sortArray(int[] nums) {
        /**
         * 排序数组-使用快排进行解决*/
        quickSort(0, nums.length-1, nums);
        return nums;
    }

    public static void quickSort(int left, int right, int[] nums) {
        /**
         * 三路快速排序递归实现*/
        // 1 递归出口
        if(left >= right) {
            return;
        }

        // 2 确定基准值
        int baseIndex = left + random.nextInt(right - left + 1);
        int baseVal = nums[baseIndex];

        // 3 分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < baseVal) {
                // -小于
                swap(i, ++l, nums);
            } else {
                // -若是大于
                while(r > i && nums[i] > baseVal) {
                    swap(i, --r, nums);
                }
                if(nums[i] < baseVal) {
                    swap(i, ++l, nums);
                }
            }
            i++;
        }

        // 4 向左右区间递归
        quickSort(left, l, nums);
        quickSort(r, right, nums);
    }

    public static int partition(int left, int right, int[] nums) {
        /**
         * 使用数组分三块的思想对区间进行划分
         * 遇见问题：使用分三块的逻辑超时*/
        // 1 确定基准值
        int baseIndex = left + random.nextInt(right - left + 1);
        int baseVal = nums[baseIndex];

        // 2 分三块
        int l = left - 1;
        int r = right + 1;
        int i = left;
        while(i < r) {
            if(nums[i] < baseVal) {
                // -小于
                swap(i, ++l, nums);
            } else {
                // -若是大于
                while(r > i && nums[i] > baseVal) {
                    swap(i, --r, nums);
                }
                if(nums[i] < baseVal) {
                    swap(i, ++l, nums);
                }
            }
            i++;
        }

        // 3 返回值
        return r-1;
    }
}

